package com.lei.sort;

import com.lei.linearsearch.ArrayGenerator;

import java.util.Arrays;

/**
 * @Author LeiXiaoLei
 * @Date 2022/7/30 09:38
 * @Version 1.0
 */
public class MergeSort {
    private MergeSort() {
    }

    // 自底向下
    public static <E extends Comparable<E>> void sort(E[] arr) {
        E[] temp = Arrays.copyOf(arr, arr.length);
        innerSort(arr, 0, arr.length, temp);
    }


    // 自底向上
    public static <E extends Comparable<E>> void sortBU(E[] arr) {
        E[] temp = Arrays.copyOf(arr, arr.length);
        int n = arr.length;
        for (int i = 0; i < n; i += 16)
            InsertionSort.sort4(arr, i, Math.min(n - 1, i + 15));
        for (int sz = 16; sz < n; sz += sz) {
            for (int i = 0; i + sz < n; i += sz + sz)
                if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0)
                    merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1), temp);
        }
    }

    private static <E extends Comparable<E>> void innerSort(E[] arr, int l, int r, E[] temp) {
        if (r - l <= 1) return;
//        if (r - l < 16) {
//            InsertionSort.sort(arr, l, r);
//            return;
//        }
        int mid = l + (r - l) / 2;
//        innerSort(arr, l, mid + 1, temp);
//        innerSort(arr, mid , r, temp);
//        if (arr[mid - 1].compareTo(arr[mid + 1]) > 0)
//            merge(arr, l, mid, r, temp);
        innerSort(arr, l, mid, temp);
        innerSort(arr, mid, r, temp);

        if(arr[mid - 1].compareTo(arr[mid]) > 0)
            merge(arr, l, mid, r, temp);
    }

    // 合并两个有序的区间 arr[l, mid] 和 arr[mid + 1, r]
//    public static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {
//        System.arraycopy(arr, l, temp, l, r - l + 1);
//        int i = l, j = mid + 1;
//        for (int k = l; k <= r; k++) {
//            if (i > mid) {
//                arr[k] = temp[j];
//                j++;
//            } else if (j > r) {
//                arr[k] = temp[i];
//                i++;
//            } else if (temp[i].compareTo(temp[j]) <= 0) {
//                arr[k] = temp[i];
//                i++;
//            } else {
//                arr[k] = temp[j];
//                j++;
//            }
//        }
//    }

    // // 合并两个有序的区间 arr[l, mid) 和 arr[mid, r)
    public static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {
        System.arraycopy(arr, l, temp, l, r - l);
        int i = l, j = mid;
        for (int k = l; k < r; k++) {
            if (i >= mid) {
                arr[k] = temp[j++];
            } else if (j >= r) {
                arr[k] = temp[i++];
            } else if (temp[i].compareTo(temp[j]) <= 0) {
                arr[k] = temp[i++];
            } else {
                arr[k] = temp[j++];
            }
        }
    }

//    private static <E extends Comparable<E>> void innerSort(E[] arr, int l, int r) {
//        if (l >= r) return;
//        int mid = l + (r - l) / 2;
//        innerSort(arr, l, mid);
//        innerSort(arr, mid + 1, r);
//        merge(arr, l, mid, r);
//    }
//    public static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
//        E[] temp = Arrays.copyOfRange(arr, l, r + 1);
//        int i = l, j = mid + 1;
//        for (int k = l; k <= r; k++) {
//            if (i > mid) {
//                arr[k] = temp[j - l];
//                j++;
//            } else if (j > r) {
//                arr[k] = temp[i - l];
//                i++;
//            } else if (temp[i - l].compareTo(temp[j - l]) <= 0) {
//                arr[k] = temp[i - l];
//                i++;
//            }else {
//                arr[k] = temp[j - l];
//                j++;
//            }
//        }
//    }

    public static void main(String[] args) {
//        Integer[] arr = {2, 3, 1, 5, 7, 1, 2};
//        MergeSort.sortBU(arr);
//        System.out.println(Arrays.toString(arr));
        int[] dataSize = {10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
        for (int n : dataSize) {
            Integer[] arr = ArrayGenerator.generatorRandomArray(n, n);
            SortingHelper.sortTest(MergeSort.class, arr);
        }
    }

}
